package util

func MinDistance(text1 string, text2 string) int {
	// 将字符串转换为rune数组以支持多字节字符（如中文）
	word1 := []rune(text1)
	word2 := []rune(text2)
	m, n := len(word1), len(word2)

	// 创建一个(m+1) x (n+1)的二维数组
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// 初始化边界条件
	for i := 0; i <= m; i++ {
		dp[i][0] = i // word1变为空字符串需要删除i个字符
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j // 空字符串变为word2需要插入j个字符
	}

	// 填充dp数组
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1] // 字符相同，无需操作
			} else {
				dp[i][j] = minInTree(
					dp[i-1][j]+1,   // 删除word1[i]
					dp[i][j-1]+1,   // 插入word2[j]
					dp[i-1][j-1]+1, // 替换word1[i]为word2[j]
				)
			}
		}
	}

	return dp[m][n]
}

// 辅助函数，返回三个数中的最小值
func minInTree(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
		return c
	}
	if b < c {
		return b
	}
	return c
}
